package com.barry.algorithm.sort;

/**
 * 类功能描述：交换排序
 *
 * @author WangXueXing create at 19-9-4 下午4:52
 * @version 1.0.0
 */
public class ExchangeSort {
    /**
     * 冒泡排序算法
     * 介绍：
     * 冒泡排序的原理非常简单，它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
     *
     * 步骤：
     * 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
     * 对第0个到第n-1个数据做同样的工作。这时，最大的数就“浮”到了数组最后的位置上。
     * 针对所有的元素重复以上的步骤，除了最后一个。
     * 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
     *
     * 原理是临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样一趟过去后,最大或最小的数字被交换到了最后一位,然后再从头开始进行两两比较交换,直到倒数第二位时结束
     * @param a 被排序的数组
     * 最坏情况：O(n2)  如果未优化的冒泡排序，最好情况也是O（n2），优化后最好情况是O（n）
     */
    public static void bubbleSort(int[] a){
        int len = a.length;
        for(int i=0;i<len-1;i++){ //一趟比较
            for(int j=0;j<len-1-i;j++){ //一次比较,每次把最大值放在最后面，所以下一次比较的时候不用对后i个数比较了
                int temp = a[j];
                if(a[j] > a[j+1]){
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
        }
        System.out.println("冒泡排序：");
        for (int i : a) {
            System.out.print(i+" ");
        }
    }

    /**
     * 优化1：某一趟遍历如果没有数据交换，则说明已经排好序了，因此不用再进行迭代了。用一个标记记录这个状态即可（程序如下）。
     * 优化2：记录某次遍历时最后发生数据交换的位置，这个位置之后的数据显然已经有序，不用再排序了。因此通过记录最后发生数据交换的位置就可以确定下次循环的范围了（上面程序中" j<=len-1-i" 实现）。
     * @param a
     */
    public static void betterBubbleSort(int[] a){
        int len = a.length;
        boolean flag = true;
        for(int i=0;i<len-1 && flag;i++){ //一趟比较 如果上趟比较一次也没有交换，则说明后面都排好序了，不用再比较了
            flag = false;
            for(int j=0;j<len-1-i;j++){ //一次比较,每次把最大值放在最后面，所以下一次比较的时候不用对后i个数比较了
                int temp = a[j];
                if(a[j] > a[j+1]){
                    a[j] = a[j+1];
                    a[j+1] = temp;
                    flag = true;
                }
            }
        }
        System.out.println("优化后的冒泡排序：");
        for (int i : a) {
            System.out.print(i+" ");
        }
    }


    /**
     * 快速排序算法
     *
     *
     * 快速排序采用的思想是分治思想。快速排序是找出一个元素（理论上可以随便找一个）作为基准(pivot),
     * 然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值，如此作为基准的元素调整到排序后的正确位置。
     * 递归快速排序，将其他n-1个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正 确位置，排序完成。
     * 所以快速排序算法的核心算法是分区操作，即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。
     * @param a
     * O(NlogN)
     */
    public static void quickSort(int[] a){
        qsort(a,0,a.length-1);
        System.out.println("快速排序：");
        for (int k : a) {
            System.out.print(k+" ");
        }
    }
    public static void qsort(int[] nums, int left, int right) {
        if(left>right) return;
        int pivot = nums[left];
        int i = left;
        int j = right;
        while(i < j){
            while(nums[j] >= pivot && i<j){ //从右往左找比nums[i]小的数
                j--;
            }
            nums[i] = nums[j]; //找到之后交换
            while(nums[i] <= pivot && i<j){ //从左往右找比nums[j]大的数
                i++;
            }
            nums[j]  = nums[i];  //找到之后交换
        }
        //while执行完后，必然有 i==j
        nums[i] = pivot; //将基准数归位
        qsort(nums, left, i-1); //递归处理左边
        qsort(nums, i+1, right); //递归处理右边
    }

    public static void main(String[] args) {
        int[] a = new int[]{2,3,6,4,7,5,1};
        bubbleSort(a);
        System.out.println("");
        betterBubbleSort(a);
        System.out.println("");
        quickSort(a);
    }
}
